# 超时方案
# class Solution(object):
#     def largestRectangleArea(self, heights):
#         """
#         :type heights: List[int]
#         :rtype: int
#         """
#         heights_set = set(heights)
#         now_value = {}
#         max_value = {}
#         for item in heights_set:
#             now_value[item] = 0
#             max_value[item] = 0
#         for height in heights:
#             for item in heights_set:
#                 if height >= item:
#                     now_value[item] += 1
#                     if now_value[item] > max_value[item]:
#                         max_value[item] = now_value[item]
#                 else:
#                     now_value[item] = 0
#         max_height = 0
#         for item in heights_set:
#             max_height = max(max_height, max_value[item] * item)
#
#         return max_height

# 单调栈
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.append(0)
        heights.insert(0, 0)
        stack = [0]
        max_value = 0
        for i in range(1, len(heights)):
            if heights[i] >= heights[stack[-1]]:
                stack.append(i)
            else:
                while heights[stack[-1]] > heights[i]:
                    index = stack.pop()
                    max_value = max(max_value, heights[index] * (i - stack[-1] - 1))
                stack.append(i)
        return max_value


data = Solution()
heights = [2,1,5,6,2,3]
print(data.largestRectangleArea(heights))
